package main.Q1_100;

import java.util.HashSet;
import java.util.Set;

public class Q1_10 {
	public static void main(String[] args) {
		System.out.println("Question1：两数之和");
		System.out.println("Question2：两数相加");
		System.out.println("Question3：无重复字符的最长字串");
		System.out.println("Question4：寻找两个正序数组的中位数");
		System.out.println("Question5：最长回文串");
		System.out.println("Question6：N字变换");
		System.out.println("Question7：整数反转");
		System.out.println("Question8：字符串转换整数(atoi)");
		System.out.println("Question9：回文数");
		System.out.println("Question10：");
	}
}

class Question1 {
	public int[] twoSum(int[] nums, int target) {
		int[] index = new int[2];
		boolean flag = false;
		for (int i = 0; i < nums.length; i++) {
			for (int j = i + 1; j < nums.length; j++) {
				if (nums[i] + nums[j] == target) {
					flag = !flag;
					index[0] = i;
					index[1] = j;
					break;
				}
			}
			if (flag) break;
		}
		return index;
	}
}

class Question2 {
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode pre = new ListNode(0);
		ListNode cur = pre;
		int carry = 0;
		while (l1 != null || l2 != null) {
			int x = l1 == null ? 0 : l1.val;
			int y = l2 == null ? 0 : l2.val;
			int sum = x + y + carry;
			carry = sum / 10;
			sum = sum % 10;
			cur.next = new ListNode(sum);
			cur = cur.next;
			if (l1 != null)
				l1 = l1.next;
			if (l2 != null)
				l2 = l2.next;
		}
		if (carry == 1) {
			cur.next = new ListNode(carry);
		}
		return pre.next;
	}
}

class Question3 {//滑动窗口

	public int lengthOfLongestSubstring(String s) {
		char[] arr=s.toCharArray();
		int maxLength=0,left=0,right=0;
		Set<Character> set=new HashSet<>();
		while(right<arr.length) {
			if(set.contains(arr[right])) {// 右扩字符被子串包含
				maxLength=Math.max(maxLength,right-left);
				while(left<right) {// 左缩
					set.remove(arr[left]);
					if(arr[left]==arr[right]) {
						left++;
						break;
					}
					left++;
				}
			}else {
				set.add(arr[right]);
				right++;
			}
		}
		maxLength=Math.max(maxLength,right-left);
		return maxLength;
//		Set<Character> occ = new HashSet<Character>();
//		int n = s.length();
//		// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
//		int rk = -1, ans = 0;
//		for (int i = 0; i < n; ++i) {
//			if (i != 0) {
//				// 左指针向右移动一格，移除一个字符
//				occ.remove(s.charAt(i - 1));
//			}
//			while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
//				// 不断地移动右指针
//				occ.add(s.charAt(rk + 1));
//				++rk;
//			}
//			// 第 i 到 rk 个字符是一个极长的无重复字符子串
//			ans = Math.max(ans, rk - i + 1);
//		}
//		return ans;
	}
}

class Question4 {
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		double result = 0;
		int[] merge = new int[(nums2.length + nums1.length) / 2 + 1];
		int count = 0, i = 0, j = 0;
		while (count < merge.length && i < nums1.length && j < nums2.length) {
			if (nums1[i] > nums2[j]) merge[count++] = nums2[j++];
			else merge[count++] = nums1[i++];
		}
		while (count < merge.length && i < nums1.length) merge[count++] = nums1[i++];
		while (count < merge.length && j < nums2.length) merge[count++] = nums2[j++];
		if ((nums1.length + nums2.length) % 2 == 0) result = (merge[merge.length - 1] + merge[merge.length - 2]) / 2.0;
		else result = merge[merge.length - 1];
		return result;
	}
}

class Question5 {
	public String longestPalindrome(String s) {
		int length = s.length();
		char[] str = s.toCharArray();
		String result = "";
		boolean[][] dp = new boolean[length][length];
		for (int i = length - 1; i >= 0; i--) {//以i开始j结尾的字符串是否为回文串
			for (int j = i; j < length; j++) {
				if (str[i] == str[j] && ((j - i < 3) || dp[i + 1][j - 1])) dp[i][j] = true;
				if (dp[i][j] && j - i + 1 > result.length()) result = s.substring(i, j + 1);//长度大于
			}
		}
		return result;
	}
}

class Question6 {
	public String convert(String s, int numRows) {
		int rowNum = 2 * numRows - 2;
		if (numRows == 1) {
			rowNum = 1;
		}
		StringBuffer result = new StringBuffer();
		for (int j = 0; j < numRows; j++) {
			for (int i = 0; i < s.length(); i++) {
				if (i % rowNum == j || i % rowNum == rowNum - j) {
					result.append(s.charAt(i));
				}
			}
		}
		return result.toString();
	}
}

class Question7 {//需考虑反转后的结果在整数范围内

	public int reverse(int x) {
		int rev = 0;
		while (x != 0) {
			if (rev < Integer.MIN_VALUE / 10 || rev > Integer.MAX_VALUE / 10) {
				return 0;
			}
			int digit = x % 10;
			x /= 10;
			rev = rev * 10 + digit;
		}
		return rev;
	}
}

class Question8 {
	public int myAtoi(String s) {
		char[] arr = s.trim().toCharArray();
		int n = arr.length;
		long ans = 0;
		boolean isPositive = true, sign = false;
		for (int i = 0; i < n; i++) {
			char ch = arr[i];
			if (!sign && (ch == '-' || ch == '+')) {
				isPositive = ch == '-' ? false : true;
				sign = true;
				continue;
			} else if (!Character.isDigit(ch)) {
				break;
			}
			sign = true;
			ans = ans * 10 + Character.getNumericValue(ch);
			if (ans > Integer.MAX_VALUE) {
				return isPositive ? Integer.MAX_VALUE : Integer.MIN_VALUE;
			}
		}
		return isPositive ? (int) ans : (int) -ans;
//        long result=0l;
//        char[] str=s.toCharArray();
//        int start=0;
//        while (start< str.length) {
//            if (str[start]=='-') break;
//            else if (str[start]>='0'&&str[start]<='9') break;
//            start++;//寻找数字开始位置
//        }
//        if (start< str.length) {
//            int flag = str[start] == '-' ? 1 : -1;//确定原本数字符号
//            if (str[start] != '-') {
//                while (start < str.length && str[start] >= '0' && str[start] <= '9') {
//                    result = result * 10 - (str[start] - 48);
//                    start++;
//                }
//            } else {
//                start++;
//                while (start < str.length && str[start] >= '0' && str[start] <= '9') {
//                    result = result * 10 - (str[start] - 48);
//                    start++;
//                }
//            }
//            result = flag * result;
//        }
//        return (int)result;
	}
}

class Question9 {
	public boolean isPalindrome(int x) {
		String str = String.valueOf(x);
		for (int i = 0; i < str.length() / 2; i++) if (str.charAt(i) != str.charAt(str.length() - 1 - i)) return false;
		return true;
	}
}
